perm filename CMPARE[0,BGB]2 blob
sn#101476 filedate 1974-05-13 generic text, type C, neo UTF8
COMMENT ā VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 7.0 IMAGE COMPARING.
C00006 00003 COMPARING.
C00010 ENDMK
Cā;
7.0 IMAGE COMPARING.
The compare step of CRE, CMPARE, connects the polygons and
arcs of the current image with corresponding polygons and arcs of
the previous image. CMPARE solves the problem of correlating
features between two similar images and is composed four sub
sections:
1. make shape nodes for polygons.
2. compare and connect polygons one to one.
3. compare and connect polygons two to one.
4. compare and connect vertices of connected polygons.
First, the shape nodes of all the polygons of an image are
computed. The shape node contains the center of mass and the lamina
inertia tensor of a polygon. The lamina inertia tensor of a polygon
with N sides is computed by summation over N trapezoids. The
trapezoid corresponding to each side is formed by dropping
perpendiculars "up" to the top of the image frame; each such
trapezoid consists of a rectangle an a right triangle; since the
sides of polygons are directed vectors the areas of the triangles
and rectangles can be arranged to take positive and negative values
such that a summation will describe the interior region of the
polygon as positive. The equations necessary for computing the
lamina inertia tensor of a polygon are collected in a table in the
postscripts to this paper and were derived by using Goldstein's
Classical Mechanics [1] as a reference. The meaning of the inertia
tensor is that it characterizes each polygon by a rectangle of a
certain length and width at a particular location and oriention; and
of further importance such inertia tensors can be "added" to
characterize two or more polygons by a single rectangle. It is the
lamina inertia tensor rectangles that are actually compared by CRE.
Second, all the shapes of the polygons of one level of the
first image are compared with all the shapes of the polygons of the
corresponding level of the second image for nearly exact match. The
potentially (M*N/2) compares is avoided by sorting on the center of
mass locations. In CRE, which is intended for comparing sequences
of pictures of natural scenes; match for center of mass location is
tested first and most strictly, followed by match for inertia.
Pointers between matching polygons are placed in the time link
positions of the polygon nodes and the polygons are considered to be
mated in time. ~I1973,800;F8- 32 -
COMPARING.
Third, all the unmated polygons of a level are considered
two at a time and a fusion shape node for each pair is made. The
potentially (N*N/2-N) fusion shapes are avoided because there is a
maximum possible unmated inertia in the other image; lo, if there
are no unmated polygons in one image then the extra polygons of the
first image can be ignored. In the event where there are unmated
polygons in corresponding levels of the two images, the fusion
shapes of one are compared with the polygon shapes of the other.
The fusion (fission) compare solves the rather nasty problem,
illustrated in figures 9A and 9B of linking two contour polygons of
one image with a single contour polygon in the next image.
Fourth, the vertices of polygons mated in time are compared
and mated. To start a vertex compare, the vertices of one polygon
are translated, rotated and dilated to get that polygon's lamina
inertia tensor coincidant with its mate (or mates). Conceptually,
each vertex of one polygon is compared with each vertex of the other
polygon(s) and the mutually closest vertices (closer than an
epsilon) are considered to be mated. Actually the potential (N*M)
compares is avoided by a window splitting scheme similiar to that
used in hidden line elimination algorithms (like Warnock's).
The results of vertex compare and mate are illustrated in
figures 9A and 9D; the compare execution takes less than a second on
images such as the pump, blocks, and dolls that have appeared in
this paper. The applications of this compare might include the
aiming of a pixel correlation comparator (such as Quam's);
recognition and location of an expected object; or the location and
extent of an unknown object. It is this latter application that
will be described in my forthcoming thesis.